package dfs_bfs.leetcode_79;

public class BackTraceNoModify {
    public boolean exist(char[][] board, String word) {
        int rows = board.length;
        if (rows == 0) {
            return false;
        }
        int cols = board[0].length;
        // 为了不修改输入数组，使用 boolean 标记当前元素是否被选择过
        boolean[][] visited = new boolean[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (dfs(board, word, i, j, 0, visited)) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] board, String word, int i, int j, int index, boolean[][] visited) {
        int rows = board.length;
        int cols = board[0].length;
        // 所有元素都匹配成功，直接返回 true
        if (index == word.length()) {
            return true;
        }
        // 越界、不匹配
        if (i >= rows || i < 0 || j >= cols || j < 0 || board[i][j] != word.charAt(index)) {
            return false;
        }
        // visited = false 表示当前元素没有被选择过，递归可以继续进行
        if (!visited[i][j]) {
            // 选择当前元素
            visited[i][j] = true;
            boolean res =
                    dfs(board, word, i + 1, j, index + 1, visited) ||
                            dfs(board, word, i - 1, j, index + 1, visited) ||
                            dfs(board, word, i, j + 1, index + 1, visited) ||
                            dfs(board, word, i, j - 1, index + 1, visited);
            /*
                回溯，撤销选择
                例如给定字符串"ab"，搜索时从a开始 a 会被标记为true, b 会被标记true。
                如果没匹配成功，下一轮搜索从 b 开始，b 也是可以向左选择 a 的，所以 a 的状态要变回 false;
             */
            visited[i][j] = false;
            return res;
        } else {
            // 如果当前元素已经被选择过，说明匹配失败
            return false;
        }
    }
}
